#include<stdio.h>
#include<stdlib.h>

struct node
{
  int value;
  struct node *next;
}*first,*last;

void append(int x)
{
  struct node *new,*j;
  new=malloc(sizeof(struct node));
    if(new==NULL)
    {
     printf("\n\tMemory allocation error");
    }
    else
    {
      new->value=x;
      new->next=NULL;
    }
    last->next=new;
    last=new;
    
printf("List is: ");
for(j=first;j!=NULL;j=j->next)
  {
    printf("%d ",j->value);
  }
  printf("\n");
}
//********************************************************************************
void extend()
{
  int m;
  struct node *first2,*j;
  first2=malloc(sizeof(struct node));
  int i;
  int b;
  printf("Enter the number of elements of the second linked list: ");
  scanf("%d",&m);
  
  printf("Enter element: ");
  scanf("%d",&b);
  first2->value=b;
  last->next=first2;
  for(i=1;i<m;i++)
  {
    printf("Enter element: ");
    scanf("%d",&b);
   struct node *new2;
   new2=malloc(sizeof(struct node));
    if(new2==NULL)
    {
      printf("\n\tMemory allocation error");
    }
    else
    {
      new2->value=b;
      new2->next=NULL;
    }
    first2->next=new2;
    first2=new2;
    first2->next=NULL;

  }
  printf("Extended list is: ");
  for(j=first;j!=NULL;j=j->next)
  {
    printf("%d ",j->value);
  }
  printf("\n");
}
//********************************************************************************
void insert(int n)
{
  int x,y,co=0;
  printf("Enter the index number where you want to insert(index range starts from 0): ");
  scanf("%d",&x);
  if(x>n || x<0)
  {
    printf("Index out of range\n");
    exit(0);
  }
  printf("Enter element: ");
  scanf("%d",&y);
  struct node *new,*i,*j;
  new=malloc(sizeof(struct node));
  new->value=y;
  if(x==0)
  {
    new->next=first;
    first=new;
  }
  else
  {
   for(i=first;i!=NULL;i=i->next)
   {
    j=i;
    ++co;
    if(co==x)
    {
      break;
    }
  }
  new->next=j->next;
  j->next=new;
  }
  printf("New list is: ");
  for(i=first;i!=NULL;i=i->next)
  {
    printf("%d ",i->value);
  }
  printf("\n");

}
//********************************************************************************
void removee()
{
  int x,flag=0;
  struct node *i,*j;
  printf("Enter the element you want to delete: ");
  scanf("%d",&x);
  if(x==1)
  {
    first=first->next;
  }
  else
  {
      for(i=first;i!=NULL;i=i->next)
  {
    if(i->next->value==x)
    {
      flag=1;
      break;
    }
  }
  if(flag==0)
  {
    printf("Value not found in the list\n");
    exit(0);
  }
  i->next=i->next->next;
  } 
  printf("New list is: ");
  for(i=first;i!=NULL;i=i->next)
  {
    printf("%d ",i->value);
  }
  printf("\n");
}
//********************************************************************************
void pop(int n)
{
  int x,i;
  char c;
  struct node *j,*k;
  printf("Do you want to enter an index number? ");
  scanf(" %c",&c);
  if(c=='y'|| c=='Y')
 {
  printf("Enter the index number(index range starts from 0): ");
  scanf("%d",&x);
  if(x>(n-1) || x<0)
  {
     printf("Index out of range\n");
    exit(0);
  }
  if(x==0)
  {
    printf("Element popped=%d\n",first->value);
    first=first->next;
  }
  else
  {
    j=first;
    for(i=1;i<x;i++)
   {
     j=j->next;
   }
   printf("Element popped=%d\n",j->next->value);
   j->next=j->next->next;  
 }
 }
 else
 {
   for(k=first;k->next->next!=NULL;k=k->next)
   {;}
   k->next=NULL;
 }
 printf("New list is: ");
 for(j=first;j!=NULL;j=j->next)
  {
    printf("%d ",j->value);
  }
  printf("\n");
 
}
//********************************************************************************   
void indexx()
{
  int x,flag=0,co=-1;
  struct node *i;
  printf("Enter element you want to search for: ");
  scanf("%d",&x);
  for(i=first;i!=NULL;i=i->next)
  {
    co++;
    if(i->value==x)
    {
      flag=1;
      break;
    }
  }
  if(flag==0)
  {
    printf("Element not found!\n");
    exit(0);
  }
  printf("Element found at index = %d\n",co);
}
//********************************************************************************   
void count()
{
  printf("Enter the element you want to count:");
  int x,c=0;
  struct node *i;
  scanf("%d",&x);
  for(i=first;i!=NULL;i=i->next)
  {
    if(i->value==x)
    {
      c++;
    }
  }
  printf("Occurences=%d\n",c);
}
//********************************************************************************  
void sort(int n)
{
 int i,j,k,l;
 struct node *p,*q,*r;
 k=n;
 for(i=0;i<n-1;i++,k--)
 {
  p=first;
  q=p->next;
  for(j=1;j< k;j++)
  {
  if(p->value>q->value)
  {
   l=p->value;
   p->value=q->value;
   q->value=l;
  }
  r=p;
  p=p->next;
  q=q->next;
  }
 }
 printf("Sorted linked list is: ");
 for(p=first;p!=NULL;p=p->next)
 {
  printf("%d ",p->value);
 }
 printf("\n");
}
//********************************************************************************  

void reverse()
{
 struct node *i,*j,*k;
 i=NULL;
 for(k=first;k!=NULL;k=j)
 {
   j=k->next;
   k->next=i;
   i=k;       
 }
 first=i;
 printf("Reversed lined list is: ");
 for(j=first;j!=NULL;j=j->next)
 {
  printf("%d ",j->value);
 }
 printf("\n");
}  
//********************************************************************************     

void main()
{
  int i,n,c,*a;
  printf("Enter the number of elements of the linked list: ");
  scanf("%d",&n);
  a = (int *)malloc(sizeof(int)*n);
  for(i=0;i<n;i++)
  {
    printf("Enter element: ");
    scanf("%d",&a[i]);
  struct node *new;
  new=malloc(sizeof(struct node));
    if(new==NULL)
    {
      printf("\n\tMemory allocation error");
    }
    else
    {
      new->value=a[i];
      new->next=NULL;
    }
  if(first==NULL)
  {
    first=new;
    last=first;
  }
  else
  {
    last->next=new;
    last=new;
  }

}

printf("MENU:\n1.Append\n2.Extend\n3.Insert\n4.Remove\n5.Pop\n6.Index\n7.Count\n8.Sort\n9.Reverse\n");
printf("Enter your choice:");
scanf("%d",&c);
switch(c)
{
  case 1:
  {
    int x;
    printf("Enter number you want to append:");
    scanf("%d",&x);
    append(x);
    break;
  }
  case 2:
  {
    extend();
    break;
  }
  case 3:
  {
    insert(n);
    break;
  }
  case 4:
  {
    removee();
    break;
  }
  case 5:
  {
   pop(n);
   break;
  }
  case 6:
  {
    indexx();
    break;
  }
  case 7:
  {
    count();
    break;
  }
  case 8:
  {
    sort(n);
    break;
  }
  case 9:
  {
    reverse();
    break;
  }
}
}
  
  
